//
//  501. 二叉搜索树中的众数.swift
//  手撕code
//
//  Created by xiaoZuDeMeng on 2024/3/6.
//

import Foundation

//https://leetcode.cn/problems/find-mode-in-binary-search-tree/description/
//给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
//
//如果树中有不止一个众数，可以按 任意顺序 返回。
//
//假定 BST 满足如下定义：
//
//结点左子树中所含节点的值 小于等于 当前节点的值
//结点右子树中所含节点的值 大于等于 当前节点的值
//左子树和右子树都是二叉搜索树
//
//
//示例 1：
//
//
//输入：root = [1,null,2,2]
//输出：[2]
//示例 2：
//
//输入：root = [0]
//输出：[0]
//
//
//提示：
//
//树中节点的数目在范围 [1, 104] 内
//-105 <= Node.val <= 105
//
//
//进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）

/*
//! 记录结果
var res = [Int]()
//! 记录当前最大频次
var maxCount = 0
//! 前一个数
var preNum = Int.max
//! 前一个数的频次
var currentCount = 0

func 二叉搜索树中的众数(_ root: TreeNode?) -> [Int] {
  if root == nil {
    return []
  }
 
  inOrderDFS(root)
     
  //! 收尾
  if currentCount > maxCount {
    res.removeAll()
    res.append(preNum)
  } else if currentCount == maxCount {
    res.append(preNum)
  }
  return res
}

//! 中序遍历
func inOrderDFS(_ root:TreeNode?) {
  guard let root = root else {
    return
  }

  inOrderDFS(root.left)
  if root.val != preNum {
    if currentCount > maxCount {
      res.removeAll()
      maxCount = currentCount
      res.append(preNum)
    } else if currentCount == maxCount {
      res.append(preNum)
    }
  
    preNum = root.val
    currentCount = 1
  } else {
    currentCount += 1
  }

  inOrderDFS(root.right)

}
 
 */

//方法一：中序遍历
//思路与算法
//
//首先我们一定能想到一个最朴素的做法：因为这棵树的中序遍历是一个有序的序列，所以我们可以先获得这棵树的中序遍历，然后从扫描这个中序遍历序列，然后用一个哈希表来统计每个数字出现的个数，这样就可以找到出现次数最多的数字。但是这样做的空间复杂度显然不是 O(1)O(1)O(1) 的，原因是哈希表和保存中序遍历序列的空间代价都是 O(n)O(n)O(n)。
//
//首先，我们考虑在寻找出现次数最多的数时，不使用哈希表。 这个优化是基于二叉搜索树中序遍历的性质：一棵二叉搜索树的中序遍历序列是一个非递减的有序序列。例如：
//
//      1
//    /   \
//   0     2
//  / \    /
//-1   0  2
//这样一颗二叉搜索树的中序遍历序列是 {−1,0,0,1,2,2}\{ -1, 0, 0, 1, 2, 2 \}{−1,0,0,1,2,2}。我们可以发现重复出现的数字一定是一个连续出现的，例如这里的 000 和 222，它们都重复出现了，并且所有的 000 都集中在一个连续的段内，所有的 222 也集中在一个连续的段内。我们可以顺序扫描中序遍历序列，用 base\textit{base}base 记录当前的数字，用 count\textit{count}count 记录当前数字重复的次数，用 maxCount\textit{maxCount}maxCount 来维护已经扫描过的数当中出现最多的那个数字的出现次数，用 answer\textit{answer}answer 数组记录出现的众数。每次扫描到一个新的元素：
//
//首先更新 base\textit{base}base 和 count\textit{count}count:
//如果该元素和 base\textit{base}base 相等，那么 count\textit{count}count 自增 111；
//否则将 base\textit{base}base 更新为当前数字，count\textit{count}count 复位为 111。
//然后更新 maxCount\textit{maxCount}maxCount：
//如果 count=maxCount\textit{count} = maxCountcount=maxCount，那么说明当前的这个数字（base\textit{base}base）出现的次数等于当前众数出现的次数，将 base\textit{base}base 加入 answer\textit{answer}answer 数组；
//如果 count>maxCount\textit{count} > maxCountcount>maxCount，那么说明当前的这个数字（base\textit{base}base）出现的次数大于当前众数出现的次数，因此，我们需要将 maxCount\textit{maxCount}maxCount 更新为 count\textit{count}count，清空 answer\textit{answer}answer 数组后将 base\textit{base}base 加入 answer\textit{answer}answer 数组。
//我们可以把这个过程写成一个 update\text{update}update 函数。这样我们在寻找出现次数最多的数字的时候就可以省去一个哈希表带来的空间消耗。
//
//然后，我们考虑不存储这个中序遍历序列。 如果我们在递归进行中序遍历的过程中，访问当了某个点的时候直接使用上面的 update\text{update}update 函数，就可以省去中序遍历序列的空间，代码如下。
//
//作者：力扣官方题解
//链接：https://leetcode.cn/problems/find-mode-in-binary-search-tree/solutions/425430/er-cha-sou-suo-shu-zhong-de-zhong-shu-by-leetcode-/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
//复杂度分析
//
//时间复杂度：O(n)O(n)O(n)。即遍历这棵树的复杂度。
//空间复杂度：O(n)O(n)O(n)。即递归的栈空间的空间代价。
var answer = [Int]()
var base = 0
var count = 0
var maxCount = 0

func findMode(_ root: TreeNode?) -> [Int] {
    dfs(root)
    return answer
}

func dfs(_ o: TreeNode?) {
    guard let node = o else { return }
    dfs(node.left)
    update(node.val)
    dfs(node.right)
}

func update(_ x: Int) {
    if x == base {
        count += 1
    } else {
        count = 1
        base = x
    }
    if count == maxCount {
        answer.append(base)
    }
    if count > maxCount {
        maxCount = count
        answer.removeAll()
        answer.append(base)
    }
}

